package sort;

public class HeapSort {
    private static int heapSize;

    /**
     * get root's location in array A
     * @return root's location
     * @note store all heap elements using A[0..length-1]
     */
    public static int root() {
        return 0;
    }

    /**
     * get last node's location in array A
     * @return last node's location
     */
    public static int lastNodeOfHeap() {
        return heapSize - 1;
    }

    /**
     * get left child's location in array A
     * @param i current node's location in array A
     * @return left child's location
     */
    public static int left(int i) {
        return i * 2 + 1;
    }

    /**
     * get right child's location in array A
     * @param i current node's location in array A
     * @return right child's location
     */
    public static int right(int i) {
        return i*2 + 2;
    }

    private static void exchange(int[] A, int d1, int d2) {
        int temp = A[d1];
        A[d1] = A[d2];
        A[d2] = temp;
    }

    /**
     * adjust heap to ensure max heap feature
     * @param A
     * @param i
     */
    public static void maxHeapify(int[] A, int i) {
        int l = left(i);
        int r = right(i);
        int largest;

        if(l < heapSize && A[l] > A[i])
            largest = l;
        else largest = i;

        if(r < heapSize && A[r] > A[largest]) {
            largest = r;
        }

        if (largest != i) {
            // exchange A[largest] with A[i]
            exchange(A, largest, i);

            maxHeapify(A, largest); // dont forget adjust the child tree if adjust current node
        }
    }

    /**
     * build max heap
     * @param A
     */
    public static void buildMaxHeap(int[] A) {
        heapSize = A.length;

        // sweep from last non-leaf node to root node
        for (int i = A.length / 2 - 1; i >= 0; i--) {
            maxHeapify(A, i);
        }
    }

    /**
     * sort A[0..length-1]
     * @param A array to be sorted
     * @note store heap using A[0..length-1], so the root node is A[0], and the last node is A[heapSize-1]
     */
    public static void heapSort(int[] A) {
        // build max heap
        buildMaxHeap(A);

        // exchange root with last node, then max heapify the heap
        // output heap peek element to ordered array A from length-1 to 1. the left 0 should be the minimum element
        for (int i = A.length - 1; i >= 1; i--) {
            exchange(A, 0, i);
            heapSize--;
            maxHeapify(A, 0);
        }
    }
}
